package com.leetcode.problems_04;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 0018: 四数之和
 * 给定一个包含n个整数的数组nums和一个目标值target，
 * 判断nums中是否存在四个元素 a，b，c和 d，使得a + b + c + d的值与target相等？
 * 找出所有满足条件且不重复的四元组。
 *
 * 注意：答案中不可以包含重复的四元组。
 *
 * 示例 1：
 *     输入：nums = [1,0,-1,0,-2,2], target = 0
 *     输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
 * 示例 2：
 *     输入：nums = [], target = 0
 *     输出：[]
 *
 * tips：排序+双指针（类似三数之和，相比之三数之和多了一重for循环）
 *
 * 时间复杂度：O(n^3)
 *
 * @Author: WuPeng
 * @Date: 2021/5/17 3:45 下午
 */
public class FourSums {

    public static List<List<Integer>> solution(int[] arr, int target){
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(arr);

        for (int i = 0; i < arr.length; i++) {
            //去重
            if (i>0 && arr[i] == arr[i-1]) continue;
            for (int j = i+1; j < arr.length; j++) {
                //去重
                if (j > i+1 && arr[j] == arr[j-1]) continue;

                int left = j+1, right = arr.length-1;
                while (left < right){
                    int tmp = arr[i] + arr[j] + arr[left] + arr[right];
                    if (tmp < target)
                        left++;
                    else if (tmp > target)
                        right--;
                    else if (tmp == target){
                        res.add(Arrays.asList(arr[i], arr[j], arr[left], arr[right]));
                        while (left < right && arr[left+1] == arr[left]) left++;
                        while (left < right && arr[right-1] == arr[right]) right--;
                        left++;
                        right--;
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1,0,-1,0,-2,2};
//        int[] nums = {0,0,0,0};
        int target = 0;
        List<List<Integer>> results = solution(nums, target);
        System.out.println(Arrays.toString(results.toArray()));
    }
}
